/**
 * 树的非递归遍历
*/

#include "Tree.c"

#ifndef TREE_TRAVERSAL_NON_RECURSIVE
#define TREE_TRAVERSAL_NON_RECURSIVE

#define StackElementType TreeNode*
#include "Stack-Link.c"

void preorderTraversal(Tree root) {
    TreeNode* tnode = root;
    // 用链表实现可以是一个比较大的数
    Stack* stack = createStack(0x7FFFFF);
    while (tnode != NULL || !isStackEmpty(stack)) {
        while (tnode != NULL) {
            // 访问结点
            visitTreeNode(tnode);
            // 一直向左并将沿途结点压入栈
            pushStack(stack, tnode);
            tnode = tnode->left;
        }
        if (!isStackEmpty(stack)) {
            // 结点弹出堆栈
            tnode = popStack(stack);
            // 转向右子树
            tnode = tnode->right;
        }
    }
    freeStack(stack);
}

// 遇到一个结点，就把它压栈，并去遍历它的左子树；
// 当左子树遍历结束后，从栈顶弹出这个结点并访问它；
// 然后按其右指针再去中序遍历该结点的右子树。
void inorderTraversal(Tree root) {
    TreeNode* tnode = root;
    // 用链表实现可以是一个比较大的数
    Stack* stack = createStack(0x7FFFFF);
    while (tnode != NULL || !isStackEmpty(stack)) {
        while (tnode != NULL) {
            // 一直向左并将沿途结点压入栈
            pushStack(stack, tnode);
            tnode = tnode->left;
        }
        if (!isStackEmpty(stack)) {
            // 结点弹出堆栈
            tnode = popStack(stack);
            // 访问结点
            visitTreeNode(tnode);
            // 转向右子树
            tnode = tnode->right;
        }
    }
    freeStack(stack);
}

void postorderTraversal(Tree root) {
    TreeNode* tnode = root;
    TreeNode* prer = NULL;
    // 用链表实现可以是一个比较大的数
    Stack* stack = createStack(0x7FFFFF);
    while (tnode != NULL || !isStackEmpty(stack)) {
        while (tnode != NULL) {
            // 一直向左并将沿途结点压入栈
            pushStack(stack, tnode);
            tnode = tnode->left;
        }
        if (!isStackEmpty(stack)) {
            // 读取栈顶元素
            tnode = peekFirst(stack);
            if (tnode->right != NULL && tnode->right != prer) {
                // 若右子树存在，且未被访问过，转向右子树
                tnode = tnode->right;
            } else {
                tnode = popStack(stack);
                // 访问结点
                visitTreeNode(tnode);
                prer = tnode;
                tnode = NULL;
            }
        }
    }
    freeStack(stack);
}

#endif 
